/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode *slow = nullptr, *fast = nullptr, *head = nullptr, *cur = nullptr;
    ListNode* sortList(ListNode* head) {
        // write code here
        if (!head) return nullptr;
        return MergeSort(head, getMid(head, nullptr), nullptr);
    }
    
    ListNode *getMid(ListNode *start, ListNode *end) {
        slow = start, fast = start;
        while (fast != end && fast->next != end) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    
    ListNode *MergeSort(ListNode *start, ListNode *mid, ListNode *end) {
        if (start->next == end) {
            start->next = nullptr;
            return start;
        }
        return Merge(MergeSort(start, getMid(start, mid), mid), MergeSort(mid, getMid(mid, end), end));
    }
    
    ListNode *Merge(ListNode *left, ListNode *right) {
        if (left->val < right->val) {
            head = left;
            left = left->next;
        } else {
            head = right;
            right = right->next;
        }
        cur = head;
        while (left && right) {
            if (left->val < right->val) {
                cur->next = left;
                left = left->next;
                cur = cur->next;
            } else {
                cur->next = right;
                right = right->next;
                cur = cur->next;
            }
        }
        if (left) cur->next= left;
        if (right) cur->next = right;
        return head;
    }
};
